// 使用堆实现一个排序算法

/* 
  1 实现一个最大堆
  2 堆的两个性质
    1 堆时一个完全二叉树，即只有最后一层的元素才有可能是不满的，其他层都是满的
    2 堆中的节点一定大于其左右孩子的值
*/

class MaxHeap {
  constructor(compare) {
    this.compare = compare || ((a, b) => a - b);
    // 使用一个数组存值
    this.arr = [];
  }

  getSize() {
    return this.arr.length;
  }

  isEmpty() {
    return this.getSize() === 0;
  }

  parent(index) {
    return Math.floor((index - 1) / 2);
  }
  leftChild(index) {
    return Math.floor(index * 2 + 1);
  }
  rightChild(index) {
    return Math.floor(index * 2 + 2);
  }
  swap(i, j) {
    const temp = this.arr[i];
    this.arr[i] = this.arr[j];
    this.arr[j] = temp;
  }
  // 添加一个元素
  add(data) {
    this.arr.push(data);
    this.siftUp(this.arr.length - 1);
  }
  siftUp(k) {
    while (k > 0 && this.compare(this.arr[k], this.arr[this.parent(k)]) > 0) {
      // 大于父节点的值，上浮
      this.swap(k, this.parent(k));
      k = this.parent(k);
    }
  }

  findMax() {
    if (this.getSize() === 0) {
      throw new Error('heap is empty!');
    }
    return this.arr[0];
  }

  getMax() {
    const max = this.findMax();
    this.swap(0, this.getSize() - 1);
    this.arr.pop();
    this.siftDown(0);
    return max;
  }
  siftDown(k) {
    while (k < this.getSize() && this.leftChild(k) < this.getSize()) {
      let j = this.leftChild(k);
      if (
        j + 1 < this.getSize() &&
        this.compare(this.arr[j + 1], this.arr[j]) > 0
      ) {
        j = this.rightChild(k);
      }
      if (this.compare(this.arr[k], this.arr[j]) >= 0) {
        break;
      }
      this.swap(k, j);
      k = j;
    }
  }
}

class HeapSort {
  static sort(arr) {
    const heap = new MaxHeap();
    for (let data of arr) {
      heap.add(data);
    }
    for (let i = arr.length - 1; i >= 0; i--) {
      arr[i] = heap.getMax();
    }
  }

  // 堆排序可以优化，变成一个原地排序
  static sort2(data) {
    /* 
      1 先讲传入的数组变成一个最大堆（使用heapify的方式（O(n)））
    */
    if (data.length <= 1) return;

    for (let i = (data.length - 2) / 2; i >= 0; i--)
      HeapSort.siftDown(data, i, data.length);

    /* 
      2 在将数组的0和最后一个元素交换，这样最后一个元素就是最大值（排好序的），在进行一次siftDown操作，
      然后依次0和倒数第二个元素交换位置
    */

    for (let i = data.length - 1; i >= 0; i--) {
      HeapSort.swap(data, 0, i);
      HeapSort.siftDown(data, 0, i);
    } 
  }

  static siftDown(data, k, n) {
    while (2 * k + 1 < n) {
      let j = 2 * k + 1; // 在此轮循环中,data[k]和data[j]交换位置
      if (j + 1 < n && data[j + 1].compareTo(data[j]) > 0) j++;
      // data[j] 是 leftChild 和 rightChild 中的最大值

      if (data[k].compareTo(data[j]) >= 0) break;

      HeapSort.swap(data, k, j);
      k = j;
    }
  }
  static swap(arr, i, j) {
    const t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
  }
}
const arr = [11, 3, 5, 1, 6, 8, 2, 9];
console.log(HeapSort.sort(arr), arr);
